//POJ2104 静态主席树
var
    i,l,r,x,m,n,sz,tot:longint;
    root,a,num,hash:array[0..100100] of longint;
    lc,rc,s:array[0..2000100] of longint;

procedure qsort(l,r:longint);
var i,j,k,t:longint;
begin
    i:=l; j:=r; k:=num[(l+r)>>1];
    repeat
        while num[i]<k do inc(i);
        while num[j]>k do dec(j);
        if i<=j then
            begin
                t:=num[i]; num[i]:=num[j]; num[j]:=t;
                inc(i); dec(j);
            end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
end;

function find(x:longint):longint;
var l,r,mid:longint;
begin
    l:=1; r:=tot;
    while l<=r do
        begin
            mid:=(l+r)>>1;
            if hash[mid]<x then l:=mid+1 else r:=mid-1;
        end;
    exit(l);
end;

procedure insert(l,r,x:longint; var y:longint; v:longint);
var mid:longint;
begin
    inc(sz); y:=sz; s[y]:=s[x]+1;
    if l=r then exit;
    lc[y]:=lc[x]; rc[y]:=rc[x];
    mid:=(l+r)>>1;
    if v<=mid then insert(l,mid,lc[x],lc[y],v)
    else insert(mid+1,r,rc[x],rc[y],v);
end;

function ask(l,r,x,y,k:longint):longint;
var mid:longint;
begin
    if l=r then exit(l);
    mid:=(l+r)>>1;
    if s[lc[y]]-s[lc[x]]>=k then exit(ask(l,mid,lc[x],lc[y],k))
    else exit(ask(mid+1,r,rc[x],rc[y],k-(s[lc[y]]-s[lc[x]])));
end;

begin
    readln(n,m);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do num[i]:=a[i];
    qsort(1,n); tot:=1; hash[tot]:=num[1];
    for i:=2 to n do
        if num[i]<>num[i-1] then
            begin inc(tot); hash[tot]:=num[i]; end;
    for i:=1 to n do insert(1,tot,root[i-1],root[i],find(a[i]));
    for i:=1 to m do
        begin
            readln(l,r,x);
            writeln(hash[ask(1,tot,root[l-1],root[r],x)]);
        end;
end.

//ZOJ2112(动态) pascal太丑,c++:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int n,m,tot,top,size;
int v[20500],hash[20500],num[20500];
int flag[10500],a[10500],b[10500],k[10500],root[10500];
int sum[2000500],ls[2000500],rs[2000500];
int l[100],r[100],aa,bb;

inline int lowbit(int x){return x&-x;}
inline int find(int x){
    int l=1,r=tot;
    while (l<=r){
        int mid=(l+r)>>1;
        if (hash[mid]<x) l=mid+1;
        else r=mid-1;
    }
    return l;
}

inline void init(){
    n=read(),m=read();
    For(i,1,n) v[i]=read(),num[++top]=v[i];
    For(i,1,m){
        char s[10];scanf("%s",s+1);
        a[i]=read(),b[i]=read();
        if (s[1]=='Q') {k[i]=read();flag[i]=1;}
        else num[++top]=b[i];
    }
    sort(num+1,num+top+1);
    hash[++tot]=num[1];
    For(i,2,top) 
        if (num[i]!=num[i-1]) hash[++tot]=num[i];
}

void insert(int wl,int wr,int x,int &y,int c,int add){
    y=++size;
    sum[y]=sum[x]+add;ls[y]=ls[x];rs[y]=rs[x];
    if (wl==wr) return;
    int mid=(wl+wr)>>1;
    if (c<=mid) insert(wl,mid,ls[x],ls[y],c,add);
    else insert(mid+1,wr,rs[x],rs[y],c,add);
}

int query(int wl,int wr,int k){
    if (wl==wr) return wl;
    int suml=0,sumr=0;
    For(i,1,aa) suml+=sum[ls[l[i]]];
    For(i,1,bb) sumr+=sum[ls[r[i]]];
    int mid=(wl+wr)>>1;
    if (k<=sumr-suml){
        For(i,1,aa) l[i]=ls[l[i]];
        For(i,1,bb) r[i]=ls[r[i]];
        query(wl,mid,k);
    }
    else{
        For(i,1,aa) l[i]=rs[l[i]];
        For(i,1,bb) r[i]=rs[r[i]];
        query(mid+1,wr,k-(sumr-suml));
    }
}

int main(){
    init();
    For(i,1,n)
        for(int j=i;j<=n;j+=lowbit(j))
                insert(1,tot,root[j],root[j],find(v[i]),1);
    For(i,1,m){
        if (flag[i]==1){
            aa=0;bb=0;a[i]--;
            for(int j=a[i];j>0;j-=lowbit(j)) l[++aa]=root[j];
            for(int j=b[i];j>0;j-=lowbit(j)) r[++bb]=root[j];
            printf("%d\n",hash[query(1,tot,k[i])]);
        }
        else{
            for(int j=a[i];j<=n;j+=lowbit(j))
                insert(1,tot,root[j],root[j],find(v[a[i]]),-1);
            v[a[i]]=b[i];
            for(int j=a[i];j<=n;j+=lowbit(j))
                insert(1,tot,root[j],root[j],find(b[i]),1);
        }
    }
}